package org.lql.algo.codecrush.week003;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-07-30 15:44
 * @description: 25. K 个一组翻转链表 <a href="https://leetcode.cn/problems/reverse-nodes-in-k-group/description/">...</a>
 **/
public class ReverseKGroup {

    /**
     * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
     * <p>
     * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     * <p>
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], k = 2
     * 输出：[2,1,4,3,5]
     * 示例 2：
     * <p>
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], k = 3
     * 输出：[3,2,1,4,5]
     * <p>
     * <p>
     * 提示：
     * 链表中的节点数目为 n
     * 1 <= k <= n <= 5000
     * 0 <= Node.val <= 1000
     * <p>
     * <p>
     * 进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode last = dummy;

        while (head != null) {
            ListNode end = getEnd(head, k);
            if (end == null) {
                break; // 不足 k 个节点，不翻转，直接结束
            }
            ListNode nextGroupHead = end.next;

            // 断开链表
            end.next = null;

            // 翻转当前这组链表
            ListNode reversedHead = reverse(head);

            // 连接上一组尾节点和翻转后的头节点
            last.next = reversedHead;

            // head 现在是翻转后的尾节点，连接下一组链表头节点
            head.next = nextGroupHead;

            // 移动 last 和 head 指针
            last = head;
            head = nextGroupHead;
        }
        return dummy.next;
    }

    public ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            if (--k == 0) {
                return head;
            }
            head = head.next;
        }
        return null;
    }

    // 反转链表，返回新的头节点
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        ReverseKGroup reverseKGroup = new ReverseKGroup();
        ListNode listNode = reverseKGroup.reverseKGroup(head, 2);
        printList(listNode);
        ListNode listNode1 = reverseKGroup.reverseKGroup1(listNode, 2);
        printList(listNode1);
    }

    private static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public ListNode reverseKGroup1(ListNode head, int k) {
        // 结果链表
        ListNode res = new ListNode(0, head);
        // 作为初始的上一组尾结点
        ListNode last = res;
        while (head != null) {
            // 进行链表按k个分组
            ListNode end = getEnd(head, k);
            // 下一组的头结点
            if (end == null) {
                break;
            }
            ListNode nextGroupHead = end.next;
            // 组内链表反转
            reverse(head, nextGroupHead);
            // 更新组间链表结点关系
            last.next = end;
            head.next = nextGroupHead;
            last = head;
            head = nextGroupHead;
        }
        return res.next;
    }

    void reverse(ListNode head, ListNode stop) {
        ListNode last = head;
        while (head != stop) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
    }

}
